#include <iostream>
#include "CppLinkTree.h"

TreeNode::TreeNode(TreeElementType element, void(*CLearPtr)(TreeElementType))
{
    this->children = DoubleLinkList(CLearPtr);
    this->data = element;
    this->parent = NULL;
}

void TreeNode::ConnectBranch(TreeNode* parent)
{
    if(parent == NULL || this == NULL)
        return;
    this->parent = parent; //双亲指向双亲节点
    parent->children.InsertTail_DLList(this);  //
}

LinkTree::LinkTree(void(*CLearPtr)(TreeElementType))
{
    this->rootnode = new TreeNode(NULL,CLearPtr);

}

bool IsNodeEqual(void* ptr1,void* ptr2)
{
    TreeNode* node1 = (TreeNode*)ptr1; //链表里的节点
    TreeNode* node2 = (TreeNode*)ptr2; //指定结点

    return node1 == node2;
}


void TreeNode::DisconnectBranch(TreeNode* parent,TreeNode* child)
{
    if(parent == NULL || child == NULL)
        return;
    if(child->parent != parent)
    {
        printf("两个结点不是父子关系!\n");
        return ;
    }
    child->parent = NULL;
    parent->children.RemoveByElement_DLList(child,IsNodeEqual);
}



TreeNode* LinkTree::GetTreeRoot()
{
    return this->rootnode;
}

//从某个节点开始打印
void TreeNode::TravelTreeNode(int deepth,void(*funcptr)(ElementType))
{
    if(this == NULL || funcptr == NULL)
        return;
    //不是根节点
    if(this->parent != NULL)
    {
        for(int i=0;i<deepth;i++)
        printf("    ");
        if(deepth>=1)
        {
            printf("|____");
        }
        funcptr(this->data);
        std::cout<<std::endl;
    }

    DLNode* TravelPoint = this->children.GetListHead();
    while(TravelPoint->next != NULL)
    {
        TreeNode* nodedata = (TreeNode*)TravelPoint->next->data;
        nodedata->TravelTreeNode(deepth+1,funcptr);
        TravelPoint = TravelPoint->next;
    }
}


//打印树
void LinkTree::TravelTree_LTree(void(*funcptr)(ElementType))
{
    printf("\n----------------------\n");
    this->rootnode->TravelTreeNode(-1,funcptr);
    printf("----------------------\n");
}

int TreeNode::GetNodeHeight()
{
    if(this == NULL)
    return 0;



    int height = 0;
    DLNode* TravelPoint = this->children.GetListHead();
    while(TravelPoint->next != NULL)
    {
        TreeNode* newdata = (TreeNode*)TravelPoint->next->data;
        int childheight = newdata->GetNodeHeight();
        height = height>childheight? height:childheight;
        TravelPoint = TravelPoint->next;
    }
    return height+1;
}

int LinkTree::GetTreeHight()
{
     return this->rootnode->GetNodeHeight();
}

TreeNode* TreeNode::FindTreeNode(void* value,bool(funcptr)(void*,void*))
{
    if(this == NULL || funcptr == NULL)
    {
        return NULL;
    }

    //符合条件,但是不能把根节点也算进去
    if(this->parent !=NULL && funcptr(this->data,value) == true)
    {
        return this;
    }
  

    TreeNode* targetnode = NULL;
    DLNode* TravelPoint = this->children.GetListHead();
    while(TravelPoint->next != NULL)
    {
        TreeNode* newdata = (TreeNode*)TravelPoint->next->data;
        targetnode = newdata->FindTreeNode(value,funcptr);
        if(targetnode != NULL)
        {
            return targetnode;
        }
        TravelPoint = TravelPoint->next;
    }
    return targetnode;
}

TreeNode* LinkTree::SearchNode_LinkTree(void* value,bool(*funcptr)(void*,void*))
{
    return this->rootnode->FindTreeNode(value,funcptr);
}

TreeNode* TreeNode::SearchChildNode_LinkTree(void* value,bool(*funcptr)(void*,void*))
{
    DLNode* TravelPoint = parent->children.GetListHead();
    while(TravelPoint->next != NULL)
    {
        TreeNode* child = (TreeNode*)TravelPoint->next->data;
        if(funcptr(child->data,value) == true)
        {
            return child;
        }
        TravelPoint = TravelPoint->next;
    }
    return NULL;
}

ElementType TreeNode::GetNodeData()
{
    return this->data;
}
